/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/8/2 10:54
 */
// 单词搜索
    // https://leetcode.cn/problems/word-search/description/
    // dfs向四周搜索
public class Solution79 {
    boolean found = false;
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, 0, i, j, word);
                if (found) {
                    return true;
                }
            }
        }
        return false;
    }

    private void dfs(char[][] board, int suiteIndex, int i, int j, String word) {
        if (suiteIndex == word.length()) {
            found = true;
            return;
        }
        if (found) {
            return;
        }
        int m = board.length, n = board[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            return;
        }
        if (board[i][j] != word.charAt(suiteIndex)) {
            return;
        }
        // 将已遍历的设为负值,避免后续四个方向的遍历又回来
        board[i][j] = (char)-board[i][j];
        dfs(board, suiteIndex + 1, i+1, j,word);
        dfs(board,suiteIndex+1,i, j+ 1,word);
        dfs(board,suiteIndex+1,i-1,j,word);
        dfs(board,suiteIndex+1,i,j-1,word);
        // 复原
        board[i][j] = (char)-board[i][j];
    }
}
